/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/copy-list-with-random-pointer
   @Language: C++
   @Datetime: 16-02-09 05:47
   */

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

// Method 1, Copy nodes and insert into origin nodes' next, Time 213ms
class Solution {
public:
	/**
	 * @param head: The head of linked list with a random pointer.
	 * @return: A new head of a deep copy of the list.
	 * Tip:
	 * 1) copy node and insert to origin node's next
	 * 2) redirect new nodes' random points
	 * 3) split new nodes from origin list
	 */
	RandomListNode *copyRandomList(RandomListNode *head) {
		// write your code here
		RandomListNode RL(-1),*p,*t;
		for(p=head; p;){    // copy nodes in origin nodes' next
			t = p->next;
			p = p->next = new RandomListNode(p->label);
			p = p->next = t;
		}
		for(p=head; p; p=p->next->next) // redirect to randoms
			if(p->random) p->next->random = p->random->next;
		for(t=&RL,p=head; p;){  // split from origin list
			t = t->next = p->next;
			p = p->next = p->next->next;
		}
		return RL.next;
	}
};

// Method 2, Using HashMap record origin node - new node, Time 143ms
class Solution {
public:
	/**
	 * @param head: The head of linked list with a random pointer.
	 * @return: A new head of a deep copy of the list.
	 */
	RandomListNode *copyRandomList(RandomListNode *head) {
		// write your code here
		unordered_map<RandomListNode*,RandomListNode*> dict;
		RandomListNode RL(-1), *p, *t;
		for(t=&RL,p=head; p; p=p->next)
			dict[p] = t = t->next = new RandomListNode(p->label);
		for(t=RL.next,p=head; p; p=p->next){
			t->random = dict[p->random];
			t = t->next;
		}
		return RL.next;
	}
};
